Việc đóng tàu Columbia bắt đầu năm 1975 chủ yếu là ở Palmdale, California. Columbia được đặt tên từ một tàu thám hiểm nhỏ Columbia với thuyền trưởng người Mỹ Robert Gray, người đã thám hiểm tây bắc Thái Bình Dương và trở thành người chiếc thuyền Mỹ đầu tiên đi vòng quanh thế giới; cái tên cũng được đặt để vinh danh Columbia, Đơn vị Điều khiển (Command Module) của phi thuyền Apollo 11. Sau được đóng xong, trạm quỹ đạo đến Trung tâm Vũ trụ John F. Kennedy vào 25 tháng 3 năm 1979, để chuẩn bị cho lần phóng đầu tiên. Vào 19 tháng 3 năm 1981, trong suốt quá trình chuẩn bị cho một thử nghiệm trên mặt đất, năm công nhân bị ngạt thở trong một lần thanh lọc khí, làm hai người chết. Columbia luôn luôn được nhắc tới như là ngọn cờ đầu của phi đội tàu con thoi.

Chuyến bay đầu tiên của Columbia (STS-1) được chỉ huy bởi John Young (một cựu phi hành gia từ thời kì Gemini và Apollo) và được hoa tiêu bởi Robert Crippen, một người chưa từng vào không gian, nhưng đã phục vụ như là thành viên hỗ trợ trong các phi vụ Skylab và Apollo-Soyuz. Nó được phóng lên vào ngày 12 tháng 4 năm 1981, và quay lại vào 14 tháng 4 năm 1981, sau khi bay vòng quanh Trái Đất 36 lần.

Vào năm 1983, Columbia thi hành phi vụ vận hành thứ hai (STS-9) với 6 phi hành gia, bao gồm cả một phi hành gia không phải là người Mỹ, Ulf Merbold. Vào 12 tháng 1 năm 1986, Columbia cất cánh với phi hành gia người Mỹ nói tiếng Tây Ban Nha (Hispanic American) đầu tiên, Dr. Franklin R. Chang-Diaz, cũng như là dân biểu đương nhiệm đầu tiên vào không gian, Bill Nelson. Một cái cũng là lần đầu tiên khác được công bố vào 5 tháng 3 năm 1998 khi NASA chỉ định Trung tá Không quân Hoa Kỳ Eileen Collins là chỉ huy của một phi vụ Columbia trong tương lai — làm Collins trở thành chỉ huy phụ nữ của phi vụ tàu con thoi.